package ext;
import java.util.*;
import org.junit.*;

public class Byte25 {
    
    //利用nums中的数字组成小于目标的最大数字（nums每个数字都可以重复使用）
    public int maxValueLTTarget(int target, int[] nums) {
        /**
         * 贪心算法：
         * 最终结果res必定与target一样长，除非nums中每个候选数都比target的首位大(若是这样，直接得到nums中最大数字，并取
         * n-1次)。
         * 否则，找到nums中小于target首数字k的最大数字，然后第二位继续找4个最大的。
         * 否则，第一位相等，以此法找到第二位，同样的做法。
         */
        List<Integer> tmp = new ArrayList<>();
        int cur = target, n = 0;
        while (cur != 0) {
            int t = cur % 10;
            tmp.add(t);
            cur /= 10;
            n++;
        }

        Arrays.sort(nums);
        cur = tmp.get(tmp.size() - 1);
        
        int less = -1, max = -1, min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= cur) {
                less = Math.max(less, nums[i]); //不大于首位的最大数字
            }
            max = Math.max(max, nums[i]); //找到最大数位
            min = Math.min(min, nums[i]);
        }

        int res = 0;
        if (min > cur) {
            //不可能与target等长度
            for (int i = 0; i < n - 1; i++) {
                res = res * 10 + max;
            }
            return res;
        } else if (less < cur) {
            //可以找到一个比最大位小一点的数字，剩下位置全部取最大值
            res = less;
            for (int i = 0; i < n - 1; i++) {
                res = res * 10 + max;
            }
            return res;
        } else {
            //最大位与其等大，继续
        }
        return res;
    }

    public int maxValueLTTarget2(int target, int[] nums) {
        Arrays.sort(nums);
        return 0;
    }

    public int dfs(List<Integer> needs, int[] nums, int idx, int cur, boolean has) {
        if (idx == needs.size()) {
            return cur;
        }
        if (has) {
            cur = cur * 10 + nums[0];
            return dfs(needs, nums, idx + 1, cur, has);
        }
        int c = needs.get(idx);
        int less = -1;//找到小于等于他的最大数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == c) {
                less = nums[i];
                break;
            } else if (nums[i] < c) {
                less = Math.max(less, nums[i]);
            }
        }

        if (less < 0) {
            //回溯
            return -1;
        } else if (less == c) {
            cur = cur * 10 + less;
            int i = dfs(needs, nums, idx + 1, cur, has);
            if (i > 0) {

            }
        }
        return 0;
    }
    
}
